In general, a semantic representation is generated from a natural-language utterance by the following process. The natural-language utterance is processed by a speech recognizer, which is coupled to a lexicon containing a plurality of words of the natural language. The speech recognizer outputs a word graph, containing at least one, and normally multiple words from the lexicon that is hypothesized to correspond to the natural-language utterance. The word graph is input into a parser, which is coupled to a grammar for the natural language. Using this grammar, the parser constructs a parse forest during the parse.
The parse forest is then inputted into a semantic interpreter, which is coupled to a knowledge base. The semantic interpreter processes the parse forest according to a predetermined semantics and outputs at least one semantic representation corresponding to the natural language utterance.
One problem with this process is that multiple word hypotheses in the word graph combined with ambiguities in the grammar may yield a large number of parses. Thus, the parse forest may become unmanageably complex. Although techniques exist to ameliorate this problem, they may remove structures that may later turn out to be useful. Alternatively, if the parse forest is packed during the parsing process, the problem of its complexity is only deferred, since an accurate and efficient means is still required to unpack the forest for processing by the semantic interpreter.
Primarily, it would be desirable to provide a method of decoding or unpacking the individual parses stored in the packed representation of a parsed word graph to yield a forest of parse trees, preferably in an order that represents their probable correctness or usefulness according to a predetermined metric.